package offer;

import java.util.HashSet;
import java.util.Objects;
import java.util.Set;
import java.util.Stack;

/**
 * @Author Elephas
 * @Date 2022/2/5
 **/
@FunctionalInterface
public interface GetMaximumGold {
    int getMaximumGold(int[][] grid);
}
class GetMaximumGoldImpl1 implements GetMaximumGold{
    /**
     * DFS
     * @param grid
     * @return
     */
    @Override
    public int getMaximumGold(int[][] grid) {
        Set<Point> isVisited = new HashSet<>();
        int M = grid.length, N = grid[0].length;
        for (int i = 0; i < M; i++) {
            for (int j = 0; j < N; j++) {
                isVisited.add(new Point(i,j));
            }
        }
        Stack<Point> stack = new Stack<>();


        return 0;
    }
    class Point{
        int x;
        int y;
        public Point(int x, int y){
            this.x = x;
            this.y = y;
        }
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            Point point = (Point) o;
            return x == point.x && y == point.y;
        }

        @Override
        public int hashCode() {
            return Objects.hash(x, y);
        }
    }
}

/**
 *  写不出来，抄题解了
 */
class GetMaximumGoldImpl2 implements GetMaximumGold{
    final static int[][] dirs = {{-1,0},{1,0},{0,-1},{0,1}};
    int[][] grid;
    int m,n;
    int ans = 0;

    @Override
    public int getMaximumGold(int[][] grid) {
        this.grid = grid;
        this.m = grid.length;
        this.n = grid[0].length;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(grid[i][j] != 0){
                    dfs(i,j,0);
                    // 每个点都进行一次dfs，穷举
                }
            }
        }
        return ans;
    }
    private void dfs(int x,int y,int gold){
        gold += grid[x][y];
        ans = Math.max(ans,gold);
        int rec = grid[x][y];
        // 当前点设为不可访问
        grid[x][y] = 0;
        for (int d = 0; d < 4; d++) {
            int nx = x + dirs[d][0];
            int ny = y + dirs[d][1];
            if(nx >= 0 && nx < m && ny >=0 && ny < n && grid[nx][ny] > 0){
                dfs(nx,ny,gold);
            }
        }
        grid[x][y] = rec;
        //深搜结束，需要回溯，恢复现场
    }
}